#include "Grammar.h"
#include "MetaParserAux.h"

namespace GxMetaParser
{
	class SymbolAlreadyExistsException
	{};

	class IllegalGrammarException
	{};

	class TerminalRegisteredAfterNonTerminalException
	{};

	GrammarSymbol::GrammarSymbol()
		: Type(Terminal), Priority(0), Associative(Non)
	{}

	Action::Action()
		: Type(Error), ID(-1), Rule(-1)
	{}

	ProductionRule::ProductionRule()
		: Priority(0), Associative(GrammarSymbol::Non)
	{}

	bool Item::operator < (const Item & item)
	{
		if (ProductionRule < item.ProductionRule)
			return true;
		else if (ProductionRule == item.ProductionRule)
		{
			if (NextChar < item.NextChar)
				return true;
			else if (NextChar == item.NextChar)
			{
				if (Position < item.Position)
					return true;
			}
		}
		return false;
	}

	bool Item::operator >(const Item & item)
	{
		if (ProductionRule > item.ProductionRule)
			return true;
		else if (ProductionRule == item.ProductionRule)
		{
			if (NextChar > item.NextChar)
				return true;
			else if (NextChar == item.NextChar)
			{
				if (Position > item.Position)
					return true;
			}
		}
		return false;
	}

	bool Item::operator == (const Item & item)
	{
		return (item.NextChar == NextChar && item.Position == Position && item.ProductionRule == ProductionRule);
	}

	ItemSet::ItemSet(Grammar * g)
	{
		ItemsHash.SetSize(g->Rules.Count()*PositionHashSize*CharHashSize);
		Goto.SetSize(g->Symbols.Count());
		for (int i=0; i<g->Symbols.Count(); i++)
			Goto[i] = -1;
		RuleCount = g->Rules.Count();
	}

	void ItemSet::Clear()
	{
		for (int i=0; i<ItemsHash.Count(); i++)
	        ItemsHash[i].Clear();
		Items.Clear();
	}


	bool ItemSet::CombineItem(const Item & item)
	{
		int i = item.ProductionRule;
		int j = item.Position % PositionHashSize;
		int k = item.NextChar % CharHashSize;
		int id = i*PositionHashSize*CharHashSize + j * CharHashSize + k;
		if (ItemsHash[id].Combine(item))
		{
			Items.Add(item);
            return true;
		}
		return false;
	}

	bool ItemSet::ItemExists(const Item & item) const
	{
		int i = item.ProductionRule;
		int j = item.Position % PositionHashSize;
		int k = item.NextChar % CharHashSize;
		int id = i*PositionHashSize*CharHashSize + j * CharHashSize + k;
		return ItemsHash[id].Exists(item);
	}

	void ItemSet::GetNextSymbols(OrderedArray<int> & symbols, Grammar * g)
	{
		for (int i=0; i<Items.Count(); i++)
		{
			if (Items[i].Position < g->Rules[Items[i].ProductionRule]->Symbols.Count())
			{
				symbols.Combine(g->Rules[Items[i].ProductionRule]->Symbols[Items[i].Position]);
			}
		}
	}

	Grammar::Grammar()
		: StartRule(-1), ExtendedStartRule(-1)
	{
		GrammarSymbol symbol;
		symbol.Name = L"epsilon";
		symbol.Type = GrammarSymbol::Epsilon;
		Symbols.Add(symbol);

		symbol.Name = L"end";
		symbol.Type = GrammarSymbol::End;
		Symbols.Add(symbol);

		symbol.Name = L"error";
		symbol.Type = GrammarSymbol::Error;
		Symbols.Add(symbol);

	}

	int Grammar::GetEpsilonSymbolID()
	{
		return 0;
	}

	int Grammar::GetEndSymbolID()
	{
		return 1;
	}

	int Grammar::GetErrorSymbolID()
	{
		return 2;
	}

	void Grammar::EvalFirstSetOfSymbol()
	{
		bool newAdd = true;
		int epsilon = GetEpsilonSymbolID();
		while (newAdd)
		{
			newAdd = false;
			for (int i=0; i<Symbols.Count(); i++)
			{
				if (Symbols[i].Type != GrammarSymbol::NonTerminal)
				{
					newAdd = FirstSet[i].Combine(i) || newAdd;
				}
				else
				{
					for (int j=0; j<Rules.Count(); j++)
					{
						if (Rules[j]->NonTerminalID == i)
						{
							bool keepAdd = true;
							int k = 0;
							while (keepAdd && k<Rules[j]->Symbols.Count())
							{
								int curSymbol = Rules[j]->Symbols[k];
								keepAdd = FirstSet[Rules[j]->Symbols[k]].Exists(epsilon);
								for (int z=0; z<FirstSet[curSymbol].Count(); z++)
								{
									if (FirstSet[curSymbol][z] != epsilon)
										newAdd = FirstSet[i].Combine(FirstSet[curSymbol][z]) || newAdd;
								}
								k++;
							}
							if (keepAdd)
								newAdd = FirstSet[i].Combine(epsilon) || newAdd;
						}
					}
				}
			}
		}
	}

	bool Grammar::EvalFirstSet(const Array<int> &prefix, OrderedArray<int> &set, bool addEpsilon)
	{
		bool epsilon = true;
		int epsilonID = GetEpsilonSymbolID();
		int lstC = set.Count();
		for (int i=0; i<prefix.Count(); i++)
		{
			epsilon = false;
			for (int j=0; j<FirstSet[prefix[i]].Count(); j++)
			{
				if (FirstSet[prefix[i]][j] == epsilonID)
					epsilon = true;
				else
				{
					set.Combine(FirstSet[prefix[i]][j]);
				}
			}
			if (!epsilon)
				break;
		}
		if (epsilon && addEpsilon)
			set.Combine(GetEpsilonSymbolID());
		return set.Count()>lstC;
	}

	void Grammar::EvalFollowSet()
	{
		//if (StartRule == -1)
		//	throw IllegalGrammarException();
		//FollowSet[StartRule].Combine(GetEndSymbolID());
		//Array<int> beta;
		//while (1)
		//{
		//	bool addedNew = false;
		//	for (int i=0; i<Rules.Count(); i++)
		//	{
		//		for (int j=0; j<Rules[i]->Symbols.Count()-1; j++)
		//		{
		//			int symbolB = Rules[i]->Symbols[j];
		//			if (Symbols[symbolB].Type == GrammarSymbol::NonTerminal)
		//			{
		//				beta.Clear();
		//				beta.Add(Rules[i]->Symbols, j+1, Rules[i]->Symbols.Count()-j-1);
		//				addedNew = addedNew || EvalFirstSet(beta, FollowSet[symbolB], false);
		//			}
		//		}
		//		int symbolB = Rules[i]->Symbols.End();
		//		if (Symbols[symbolB].Type == GrammarSymbol::NonTerminal)
		//		{
		//			int lstC = FollowSet[symbolB].Count();
		//			for (int j=0; j<FollowSet[Rules[i]->NonTerminalID].Count(); j++)
		//			{
		//				FollowSet[symbolB].Combine(FollowSet[Rules[i]->NonTerminalID][j]);
		//			}
		//			addedNew = addedNew || (FollowSet[symbolB].Count() > lstC);
		//		}
		//	}
		//	if (!addedNew)
		//		break;
		//}
	}

	void Grammar::EvalClosure(GxMetaParser::ItemSet &I)
	{
		Array<int> prefix;
		OrderedArray<int> F;
		int lstC = I.Items.Count();
		for (int i=0; i<I.Items.Count(); i++)
		{
			Item & item = I.Items[i];
			ProductionRule * rule = Rules[item.ProductionRule].operator ->();
			prefix.Clear();
			F.Clear();
			if (item.Position < rule->Symbols.Count())
			{
				int symbolB = rule->Symbols[item.Position];
				for (int j=item.Position+1; j<rule->Symbols.Count(); j++)
					prefix.Add(rule->Symbols[j]);
				prefix.Add(item.NextChar);
				EvalFirstSet(prefix, F, false);
				for (int k=0; k<Rules.Count(); k++)
				{
					if (Rules[k]->NonTerminalID == symbolB)
					{
						for (int j=0; j<F.Count(); j++)
						{
							Item nitem;
							nitem.ProductionRule = k;
							nitem.Position = 0;
							nitem.NextChar = F[j];
							I.CombineItem(nitem);
						}
					}	
				}
			}
		}
	}

	void Grammar::EvalGotoSet(const ItemSet & I, int X, ItemSet & J, bool closure)
	{
		J.Clear();
		for (int i=0; i<I.Items.Count(); i++)
		{
			Item item = I.Items[i];
			if (item.Position < Rules[item.ProductionRule]->Symbols.Count() &&
				Rules[item.ProductionRule]->Symbols[item.Position] == X)
			{
				item.Position ++;
				J.CombineItem(item);
			}
		}
		if (closure)
		    EvalClosure(J);
	}

	void Grammar::EvalItemSets()
	{
		ItemSet * I0 = new ItemSet(this);
		Item item;
		item.NextChar = GetEndSymbolID();
		item.Position = 0;
		item.ProductionRule = ExtendedStartRule;
		I0->CombineItem(item);
		ItemSets.Add(I0);
		EvalClosure(*I0);
		OrderedArray<int> symbols;
		int i=0;
		while (i<ItemSets.Count())
		{
			bool inserted = false;
			symbols.Clear();
			ItemSets[i]->GetNextSymbols(symbols, this);
			for (int j=0; j<symbols.Count(); j++)
			{
				RefPtr<ItemSet> s = new ItemSet(this);
				EvalGotoSet(*ItemSets[i], symbols[j], *s, false);
				
				if (s->Items.Count())
				{
					bool found = false;
					int fid = -1;
					for (int k =0; k<ItemSets.Count(); k++)
					{
						bool equals = true;
						for (int l=0; l<s->Items.Count(); l++)
							if (!ItemSets[k]->ItemExists(s->Items[l]))
							{
								equals = false;
								break;
							}
						if (equals)
						{
							found = true;
							fid = k;
							break;
						}
					}
					if (!found)
					{
						EvalClosure(*s);
						ItemSets.Add(s);
						inserted = true;
						ItemSets[i]->Goto[symbols[j]] = ItemSets.Count()-1;
					}
					else
					{
						ItemSets[i]->Goto[symbols[j]] = fid;
					}
				}
			}
            i++;
		}
	}

	void Grammar::SetAction(int i, int a, const Action & act)
	{
		Action nAction = act;
		Action oAction = ParseTable->Actions[i][a];
		const Action & newAction = act;
		Action & oldAction = ParseTable->Actions[i][a];
		if (oldAction.Type == Action::Error)
		{
			oldAction = newAction;
			return;
		}
		bool equal = (newAction.ID == oldAction.ID && newAction.Type == oldAction.Type);
		if (equal)
			return;
		ProductionRule * newRule = Rules[act.Rule].operator ->();
		ProductionRule * oldRule = 0;
		if (ParseTable->Actions[i][a].Rule != -1)
			oldRule = Rules[ParseTable->Actions[i][a].Rule].operator ->();
		bool IsSameGroup = (oldRule && newRule->GroupName == oldRule->GroupName);

		if (IsSameGroup)
		{
			if (newRule->Priority > oldRule->Priority)
			{
				oldAction = newAction;
				return;
			}
			else if (newRule->Priority == oldRule->Priority)
			{
				if (newRule->Associative == GrammarSymbol::Left
					&& newAction.Type == Action::Reduct)
				{
					oldAction = newAction;
					return;
				}
				else if (oldRule->Associative == GrammarSymbol::Non)
				{
					oldAction.Type = Action::Error;
					return;
				}
			}
			return;
		}

		if (oldAction.Type == Action::Reduct && newAction.Type == Action::Shift)
		{
			oldAction = newAction;
			if (oldRule && oldRule->Symbols.Count()==0)
				return;
		}
		else if (oldAction.Type == Action::Reduct && newAction.Type == Action::Reduct)
		{
			if (oldAction.Rule > newAction.Rule)
				oldAction = newAction;
		}

		GrammarError err;
		err.NewAction = act;
		err.OldAction = ParseTable->Actions[i][a];
		err.State = i;
		err.Symbol = a;
		Errors.Add(err);
	}

	void Grammar::CreateAutomaton()
	{
		ParseTable = new Automaton();
		ParseTable->Actions.SetSize(ItemSets.Count());
		ParseTable->Goto.SetSize(ItemSets.Count());
		int terminalCount = GetTerminalSymbolCount();
		int nonTerminalCount = Symbols.Count() - terminalCount;
		ItemSet set(this);
		OrderedArray<int> symbols;
		Errors.Clear();
		for (int i=0; i<ItemSets.Count(); i++)
		{
			ParseTable->Actions[i].SetSize(terminalCount);
			ParseTable->Goto[i].SetSize(nonTerminalCount);
			for (int j=0; j<ItemSets[i]->Items.Count(); j++)
			{
				int pos = ItemSets[i]->Items[j].Position;
				ProductionRule * rule = Rules[ItemSets[i]->Items[j].ProductionRule].operator ->();
				if (pos < rule->Symbols.Count() && Symbols[rule->Symbols[pos]].Type != GrammarSymbol::NonTerminal)
				{
					int a = rule->Symbols[pos];
					Action act;
					act.Type = Action::Shift;
					act.ID = ItemSets[i]->Goto[rule->Symbols[pos]];
					act.Rule = ItemSets[i]->Items[j].ProductionRule;
					SetAction(i, a, act);
				}
				else if (pos == rule->Symbols.Count())
				{
					int a = ItemSets[i]->Items[j].NextChar;
					Action act;
					if (ItemSets[i]->Items[j].ProductionRule == ExtendedStartRule)
					{
						act.Type = Action::Accept;
						act.Rule = ItemSets[i]->Items[j].ProductionRule;
					}
					else
					{
						act.Type = Action::Reduct;
						act.ID = ItemSets[i]->Items[j].ProductionRule;
						act.Rule = ItemSets[i]->Items[j].ProductionRule;
					}
					SetAction(i, a, act); 
				}
			}
			// Fill Goto Table
			for (int j=terminalCount; j<Symbols.Count(); j++)
			{
				if (Symbols[j].Type == GrammarSymbol::NonTerminal)
				{
					int val = ItemSets[i]->Goto[j];
					ParseTable->Goto[i][j-terminalCount] = ItemSets[i]->Goto[j];
				}
			}

		}
	}

	void Grammar::Initialize(bool validate)
	{
		if (StartRule == -1)
			throw IllegalGrammarException();
		if (validate && !ValidateGrammar())
			throw IllegalGrammarException();
		Parser = 0;
		ProductionRule * rule = new ProductionRule();
		rule->Symbols.Add(Rules[StartRule]->NonTerminalID);
		rule->NonTerminalID = RegisterNonTerminalSymbol("#StartExtended");
		Rules.Add(rule);

		FirstSet.SetSize(Symbols.Count());
		FollowSet.SetSize(Symbols.Count());
		EvalFirstSetOfSymbol();
		
		ExtendedStartRule = Rules.Count()-1;
		EvalItemSets();
		CreateAutomaton();
	}

	bool Grammar::ValidateGrammar()
	{
		for (int i=0; i<Rules.Count(); i++)
		{
			for (int j=0; j<Rules[i]->Symbols.Count(); j++)
			{
				int sid = Rules[i]->Symbols[j];
				String name = Symbols[sid].Name;
				if (Symbols[sid].Type != GrammarSymbol::NonTerminal)
					continue;
				bool found = false;
				for (int k=0; k<Rules.Count(); k++)
					if (Rules[k]->NonTerminalID == sid)
					{
						found = true;
						break;
					}
				if (!found)
					return false;
			}
		}
		return true;
	}

	int Grammar::RegisterSymbol(const String & name, GrammarSymbol::SymbolType type)
	{
		if (type == GrammarSymbol::Terminal && Symbols.Count() && Symbols.End().Type == GrammarSymbol::NonTerminal)
			throw TerminalRegisteredAfterNonTerminalException();
		for (int i=0; i<Symbols.Count(); i++)
		{
			if (Symbols[i].Name == name)
			{
				throw SymbolAlreadyExistsException();
			}
		}
		GrammarSymbol symbol;
		symbol.Type = type;
		symbol.Name = name;
		Symbols.Add(symbol);
		return Symbols.Count()-1;
	}

	int Grammar::GetTerminalSymbolCount()
	{
		for (int i=0; i<Symbols.Count(); i++)
		{
			if (Symbols[i].Type == GrammarSymbol::NonTerminal)
			{
				return i;
			}
		}
		return Symbols.Count();
	}

	int Grammar::RegisterNonTerminalSymbol(const String &name)
	{
		return RegisterSymbol(name, GrammarSymbol::NonTerminal);
	}

	int Grammar::RegisterTerminalSymbol(const String &name)
	{
		return RegisterSymbol(name, GrammarSymbol::Terminal);
	}

	GrammarSymbol * Grammar::GetRegisteredSymbol(const String & name)
	{
		for (int i=0; i<Symbols.Count(); i++)
		{
			if (Symbols[i].Name == name)
			{
				return &Symbols[i];
			}
		}
		return 0;
	}

	int Grammar::GetSymbolID(const String & name)
	{
		for (int i=0; i<Symbols.Count(); i++)
		{
			if (Symbols[i].Name == name)
			{
				return i;
			}
		}
		return -1;
	}

	bool Grammar::ParseProfile(const String &profile)
	{
		GrammarParser parser(this);
		return parser.Parse(profile);
	}

	bool Grammar::AddRule(const String &rule)
	{
		if (!Parser)
			Parser = new GrammarParser(this);
		int lastCount = Rules.Count();
		bool rs = Parser->Parse(rule);
		if (rs)
		{
			for (int i=lastCount; i<Rules.Count(); i++)
			{
				Rules[i]->OnReduction = CopyObject<0>();
			}
		}
		return rs;
	}

	bool Grammar::AddRule(const String &rule, const GxMetaParser::ReductionEventHandler &handler)
	{
		if (!Parser)
			Parser = new GrammarParser(this);
		int lastCount = Rules.Count();
		bool rs = Parser->Parse(rule);
		
		if (rs)
		{
			for (int i=lastCount; i<Rules.Count(); i++)
			{
				Rules[i]->OnReduction = handler;
			}
		}
		return rs;
	}

	

}